#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn=22;
vector<int> adj[maxn];
int dp[1<<maxn][maxn];

int gcd(int a, int b){
	while (a%b) {
		int tmp=a%b;
		a=b;
		b=tmp;
	}
	return b;
}

void solve(){
	for(int i=1;i<=21;i++){
		for(int j=i+1;j<=21;j++){
			if(gcd(i, j)==1){ // 互质
				// 存图
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	
	// 状压 DP 先记得初始化
	dp[1][1]=1; // 初始位置
	
	int range=1<<21;
	for(int i=1;i<range;i++){ // 枚举所有的状态
		for(int j=1;j<=21;j++){ // 当前所处位置
			if(((i>>(j-1))&1)){ // 位置必须合法,当前位置需要为 1
				for(int nex: adj[j]){ // 向其他位置贡献
					if(((i>>(nex-1))&1)==0){ // 还没有走过
						dp[i|(1<<(nex-1))][nex]+=dp[i][j];
					}
				}
			}
		}
	}
	
	int ans=0;
	for(int i=1;i<=21;i++){ // 所有位置都能回到 1
		ans += dp[range-1][i]; // 所有位置都必须走过
	}
	
	cout<<ans<<'\n';
	
}


signed main(){
	ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
	solve();
	return 0;
}
